/**
 * 二叉树，树节点数据结构
 * 左边节点的数据小于右边节点的数据
 */
function Node(data, left, right) {
	this.left = left;  //节点的左节点
	this.right = right;  //节点的有节点
	this.data = data;  //  节点的数据
	this.show = show;  // 显示节点的值
}


function show() {
	return this.data;
}

//  二叉树
function BST() {
	this.root = null;
	this.insert = insert;
	this.middleForEach = middleForEach;  // 中序遍历（中根遍历）
	this.preForEach = preForEach;  //先序遍历（先根遍历）
	this.postForEach = postForEach;  //后根遍历
	this.getMinValue = getMinValue;  //获取二叉树的最小值
	this.getManValue = getManValue;  //获取二叉树最大值
	this.find = find;
	this.toString = toString;
}


/**
 二叉树插入算法

(1) 设根节点为当前节点。
(2) 如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反
之,执行第 4 步。
(3) 如果当前节点的左节点为 null,就将新的节点插入这个位置,退出循环;反之,继续
执行下一次循环。
(4) 设新的当前节点为原节点的右节点。
(5) 如果当前节点的右节点为 null,就将新的节点插入这个位置,退出循环;反之,继续
执行下一次循环。

亲，拿张纸画画更容易理解哦！
*/
function insert(data) {
	// 首先构建插入节点
	var newNode = new Node(data, null, null);  //左右节点暂时设置为 null，因为还不知道左右节点是那个
	//  设置根节点为当前节点
	var currNode = this.root;
	// 判断根节点是否为空，如果跟节点为空，直接把插入的节点设置为根节点
	if (null == this.root) {
		this.root = newNode;
	} else {
		var tmp = null;
		while (true) {
			tmp = currNode; //当前节点 tmp 会随着 currNode 改变而改变
			// 如果当前节点大于插入的节点，则设置插入节点为左节点，反之
			if (data > currNode.data) {
				currNode = currNode.right;  //  这句代码实现了类似于自增的功能，逐步遍历
				if (null == currNode) {  // 一直向下遍历，知道找到左节点或者是右节点是空的节点
					tmp.right = newNode;  //找到右节点为空的元素后，把要插入的节点作为其右节点

					break;  //退出循环
				}
			} else {  //如果插入的元素的值小于当前节点的值
				currNode = currNode.left;  // 使得 currNode 这个“指针”不断深入遍历树的节点
				if (null == currNode) {
					tmp.left = newNode;

					break;
				}
			}
		}
	}
}


//  中序遍历，从根节点开始，使用递归遍历
function middleForEach(node) {
	if (null != node) {
		middleForEach(node.left);  //先遍历左子树
		print(node.show() + ", ");
		middleForEach(node.right);  //遍历右子树
	}
}

// 先序遍历
function preForEach(node) {
	if (null != node) {
		print(node.show() + ", ");
		preForEach(node.left);
		preForEach(node.right);
	}
}

// 先序遍历
function postForEach(node) {
	if (null != node) {
		postForEach(node.left);
		postForEach(node.right);
		print(node.show() + ", ");
	}
}

// 查找最小值和最大值
//  最小值一定是在左子树的最后一个左子结点
function getMinValue() {
	var currNode = this.root;  //设置当前的“指针”指向根节点
	while (null != currNode.left) {
		currNode = currNode.left;
	}
	//  一直循环，直到找到某一个节点的左节点是空的节点
	return currNode.data;
}



//  最大值一定是在左子树的最后一个右子结点
function getManValue() {
	var currNode = this.root;
	while (null != currNode.right) {
		currNode = currNode.right;
	}

	return currNode.data;
}

//  根据节点的值查找节点
//  实现代码其实是把查找最大最小值的代码组合起来
function find(data) {
	var currNode = this.root;
	while (null != currNode) {
		if (currNode.data > data) {  // 如果当前节点的值大于查找的值，说明查找的值肯定是在左子树
			currNode = currNode.left;  //  指向左子树
		} else if (currNode.data < data) {  // 如果当前节点的值小于查找的值，说明查找的值肯定是在有子树
			currNode = currNode.right;
		} else {  //  当前节点的值与查找的值相等
			return currNode;  //返回找到的节点
		}
	}
	// 如果遍历完二叉树还是没找到，说明不存在这个节点
	return null;
}


function toString(node) {
	print(node.data);
}

/**
 从 BST 上删除节点的操作最复杂,其复杂程度取决于删除哪个节点。
 如果删除没有子节点 的节点,那么非常简单。如果节点只有一个子节点,不管是左子节点还是右子节点,就变 得稍微有点复杂了。
 删除包含两个子节点的节点最复杂。
为了管理删除操作的复杂度,我们使用递归操作,同时定义两个方法:remove() 和 removeNode()。
从 BST 中删除节点的第一步是判断当前节点是否包含待删除的数据,如果包含,则删除该 节点;
如果不包含,则比较当前节点上的数据和待删除的数据。如果待删除数据小于当前 节点上的数据,
则移至当前节点的左子节点继续比较;如果删除数据大于当前节点上的数 据,则移至当前节点的右子节点继续比较。
如果待删除节点是叶子节点(没有子节点的节点),那么只需要将从父节点指向它的链接 指向 null。
如果待删除节点只包含一个子节点,那么原本指向它的节点久得做些调整,使其指向它的 子节点。
最后,如果待删除节点包含两个子节点,正确的做法有两种:要么查找待删除节点左子树 上的最大值,
要么查找其右子树上的最小值。这里我们选择后一种方式。

*/
function remove(data) {
	root = removeNode(this.root, data);
}

function removeNode(node, data) {
	if (null == node) 
		return null;
	if (node.data == data) {
		// 找到要删除的节点，判断要删除的节点是否有左右子节点
		if (null == node.left && null == node.right) {  // 左右子节点都没有
			return null;
		} else if (null == node.left) {  //没有左子结点
			return node.right;
		} else if (null == node.right) {  //没有右子节点
			return node.left;
		} else {  //左右节点都有
			var tmpNode = getSmaller(node.right);
			node.data = tmpNode.data;
			node.right = remove(this.right, tmpNode.data);
			return node;
		}
	} else if (node.data > data) {  // 当前节点大于要删除的节点的数据，所有删除的节点肯定是在当前节点的左子树
		node.left = remove(node.left, data);
		return node;
	} else {  // node.data < data
		node.right = remove(node.right, data);
		return node;
	}
}



var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(1);
nums.insert(37);
nums.insert(327);
nums.insert(3);
nums.insert(99);
nums.insert(22);
print("中序遍历: ");
middleForEach(nums.root);


print("\n先序遍历: ");
preForEach(nums.root);


print("\n后序遍历: ");
postForEach(nums.root);


//  测试
print("\n最小值：");
print(nums.getMinValue());

print("\n最大值：");
print(nums.getManValue());

print("\n查找值为99的节点");
var n = nums.find(99);
if (null != n) {
	print("找到节点：" + n.toString(n.node));
} else {
	print("节点不存在！");
}



